Static timing analysis (STA) has been used to verify the timing correctness of VLSI circuits. Voltage waveforms are propagated from primary inputs of the circuit to determine the earliest and latest possible signal arrival times/voltage waveforms as seen at the primary outputs. As the Complementary Metal-Oxide Semiconductor (CMOS) process technologies continue to scale down towards the nanometer domain, the accuracy of the static timing analysis becomes more challenging due to electrical parasitic effects, one being the Miller capacitance. The floating capacitance existing between the input and outputs of a CMOS gate is referred to as Miller capacitance which causes the CMOS gate dynamic input capacitance to become greater than the static parasitic capacitance.
VLSI circuits are typically formed by CMOS gates interconnected by way of wires/interconnect networks. Most STA tools break the timing analysis of these VLSI circuits into two parts: gate timing analysis, namely, the gate propagation delay and output transition times (also referred to as slew analysis), and interconnect or wire timing analysis, i.e., interconnect propagation delay and output transition times (slew) analysis.
Various Model Order Reduction (MOR) techniques have been described, e.g., by L. T. Pillage and R. A. Rohrer, “Asymptotic waveform evaluation for timing analysis,” IEEE Trans. on Computer Aided Design, vol. 9, 1990, pp. 352-366, and by A. Odabasioglu, M. Celik, and L. T. Pileggi, “PRIMA: passive reduced-order interconnect macro-modeling algorithm,” Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, San Jose, Calif., pp. 58-65, 1997, which have found application for accurate interconnect timing analysis.
On the other hand, for gate timing analysis, the load as seen by the driving gate is modeled by a reduced order model interconnect, such as the RC-π model (that includes the input capacitance of the fan-out gates), as described by P. R. O'Brien and T. L. Savarino, “Modeling the driving-point characteristic of resistive interconnect for accurate delay estimation,” Proc. of International Conference on Computer Aided Design, pp. 512-515, 1989. It is worth noting that gate timing analysis will result when calculating the voltage waveform/propagation delay/output slew at the output of the gate driving the RC-π load. Thus, the interconnect propagation delay and output slew are determined by fitting a ramp or a piece-wise-linear waveform obtained at the gate timing analysis step and convolving it with the transfer function of the interconnect/wire reduced order model (it also includes the input capacitance of the fan-out gates). The stage delay (a.k.a. timing stage) is defined as the delay from the input of a CMOS gate/cell to the input of each CMOS gate/cell fanning-out from the primitive gate.
STA has a linear complexity with respect to the number of gates in a design by propagating the arrival times/required arrival times/voltage waveforms through the gates and interconnects, assuming that the timing stages are independent from each other, i.e., it considers a fixed load for the input capacitance of the receiving gates while calculating the RC-π load (for the gate timing analysis step) and interconnect transfer function ROM (for the interconnect timing analysis). However, due to the dynamic effect of the Miller capacitance on timing, this assumption is not valid. In reality, the input capacitance of the CMOS gate varies dynamically during the voltage waveform transition depending on how the signals rise and fall at the two end-terminals of the CMOS gates (i.e., the input and the output of the gates). Consequently, the Miller capacitance effect can cause changes to the calculated RC-π model (which is driven by the CMOS gate) and calculated interconnect ROM (for interconnect timing analysis). Hence, calculating the voltage waveform at the output of a gate/cell can change the input capacitance of the gate and affect the voltage waveforms at the timing points of previous timing stages. The present invention addresses this issue by way of a new STA to achieve high accuracy with respect to ‘golden’ circuit simulator (i.e., SPICE.)
Miller Capacitance and its Significance on Timing
Referring now to FIG. 1(a), the gate capacitances are generally classified into three categories: 1) the input-capacitance to ground 101; 2) the output-capacitance to ground 102; and 3) the Miller capacitance 103. The floating capacitance existing between input and output ports of a CMOS gate/driver is referred to as Miller capacitance, because this capacitance causes the dynamic input capacitance of the CMOS gate to become greater than the static parasitic capacitance to ground. The aforementioned capacitance values 101, 102, 103, are calculated during library characterization and are typically stored in the gate timing library.
Miller capacitance provides a direct path for the electrical signals from the inputs 104 of a CMOS gate to its outputs 105, and vice versa. This direct path implies that the timing stages are not independent from each other, and a signal transition at output 105 of the CMOS gate may affect the timing results at inputs 104 of the gate or even at the timing points of the previous stages of the design.
The Miller capacitance value and its effect on timing differ for various types of CMOS gates. For instance, considering CMOS inverter 106 shown in FIG. 1(b), it is possible that a CMOS inverter has a large Miller capacitance value 107, while a CMOS buffer 108 (FIG. 1(c)), which is made by cascading two of the same CMOS inverters 110 and 111, has a smaller Miller capacitance value 109 that may force a weaker Miller capacitance effect on the timing results. This fact is observed for other CMOS gates as well. Referring to FIG. 1(d), the Miller capacitance from inputs of a multi-input gate to its output ports can vary widely. For instance, for the case of NAND2 gate 112, the Miller capacitance 113 from the input closest to the output in the stack may be larger than the Miller capacitance 114 from the input farthest to the output. In addition, even the transistor size of the CMOS gates can impact the Miller capacitance. Hereinafter, the effect of Miller capacitance on timing will be described in detail for a given a circuit structure, and metrics will be described to determine when the Miller capacitance effect on its timing is significant.
Static Timing Analysis of VLSI Circuits
Referring to FIG. 2(a), most STA tools break the analysis into two parts: 1) gate timing analysis 201, (i.e., gate propagation delay and output slew calculation), and 2) interconnect timing analysis 202, (i.e., interconnect propagation delay and output slew calculation). The overall delay from input A of the CMOS inverter 208 to the input C of the NAND2 gate 207 is expressed as the sum of the gate delay from input A to the output B of CMOS inverter 208, and interconnect propagation delay from output B of the inverter 208 to the input C of the NAND2 gate 207, as shown in EQ. 1. Therefore, the stage delay 210 is defined as the delay from the voltage waveform 204 at the input of CMOS gate 208, to the voltage waveform 209 at the input of each gate 207 in the fan-out of the primitive gate 208.DelayAC=DelayAB+DelayBC   EQ. 1Interconnect Timing Analysis
The voltage waveform 209 at the sink terminals of the interconnect network 205 is a function of the voltage waveform 203 at the input of interconnect network 205 (i.e., the voltage waveform 203 at the output of gate 208 connected to the input of the interconnect network), interconnect parasitics 205, and input capacitance 206 of each gate 207 at the outputs of the interconnect network. The interconnect impulse response is a function of the interconnect parasitics, (i.e., the resistances and capacitances of interconnect 205) as well as the input capacitance 206 of all the gates 207 connected to the sink terminals of the interconnect network. The interconnect delay and output slew is calculated by fitting a ramp or a piece-wise-linear waveform to the voltage waveform 203 at the input of the interconnect network and convolving it with the transfer function of the interconnect.
Various Model Order Reduction (MOR) techniques such as those described by L. T. Pillage and R. A. Rohrer, “AWE: Asymptotic waveform evaluation for timing analysis,” IEEE Trans. on Computer Aided Design, vol. 9, 1990, pp. 352-366, and those described by A. Odabasioglu, M. Celik, and L. T. Pileggi, “PRIMA: passive reduced-order interconnect macro-modeling algorithm,” Proceedings of the IEEE/ACM international conference on Computer-Aided Design San Jose, pp. 58-65, 1997, both having been advanced for accurate interconnect timing analysis. Model Order Reduction (MOR) techniques reduce the complexity of the large-scale interconnect networks to smaller ones while preserving their input-output behavior. In other words, the large-scale interconnect networks are reduced to a smaller interconnect network, such that when the same input signal is applied to both, the original interconnect network and the ensuing reduced order model will have their output response closely matched to each other. Note that higher order reduced models display a similar behavior on the original interconnect network while, although they add complexity to the analysis. For instance, a first reduced order model can be very fast to be analyzed while it may destroy the input-output behavior of the system. Therefore, there exists a trade-off between accuracy and speed for determining the order of the reduced model.
As mentioned earlier, the voltage waveform 209 at the output of the interconnect network is also a function of the input capacitance of gates 206 connected to the outputs of the interconnect. Furthermore, the input capacitance 206 of the gates is not fixed and varies during the voltage transition at the input and outputs 209 and 214 of the gate due to the existence of the Miller capacitance between the gate input and outputs. The magnitude of the input capacitance variation is a function of multiple factors including: 1) the voltage waveform at the input of the gate 209; 2) the voltage waveform at the output of gate 214; 3) the relative time difference between the input voltage waveform 209; and the output voltage waveform 214; 4) the Miller capacitance value, and the like. This implies that in order to accurately calculate the voltage waveform at outputs 209 of the interconnect, one needs to first calculate the voltage waveform at outputs 214 of gates 207, at the fan-out of the interconnect network. Further discussion about the Miller capacitance on the timing will be deferred to later.
Gate Timing Analysis
The gate output voltage waveform 203 is a function of several parameters, including the voltage waveform 204 at the input terminal of the gate which is propagated from the previous stages of the design, the output load parasitics 205 and 206, (i.e., the resistance and capacitance of the load 205 as well as the input capacitance 206 of each gate 207 in the fan-out of the primitive gate 208), and the primitive gate 208 timing characteristics. Therefore, given the input voltage waveform 204, the gate timing library, the load parasitics 205, and the input capacitance 206 of the fan-out gates of primitive gate 208, the gate timing analysis calculates the gate output voltage waveform 203 characteristics with respect to those of the gate input voltage waveform 204 (e.g., the gate propagation delay and output slew).
Different gate/driver modeling techniques exist for gate timing analysis. Three well known are based on: (1) the use of delay and slew polynomial equations characterized as a function of input slew, output capacitive load, manufacturing process parameters (e.g., NP-skew, doping concentration, and the like), and environmental parameters (e.g., Vdd, temp); (2) the use of delay and slew tables characterized as a function of input slew and output capacitive load; (3) the use of current source models where the model itself is independent from input events (i.e., the input slew) and output events (i.e., output load).
The first and second modeling techniques are more efficient than the third one. However, they do not accurately capture the effect of Miller capacitance on timing while the third technique does. In the following, highlights of these techniques will be discussed.
Gate Timing Analysis Using Delay and Slew Tables/Equations
As mentioned earlier, the delay and slew tables (FIG. 3(a)) and equations (FIG. 3(b)) in the first and second modeling techniques are characterized as a function of input slew and output capacitive load. It is assumed that the slew at the input of a gate is given. If the load at the output of the gate is approximated by a capacitive load, using the delay table/equation in the gate library, the gate propagation delay can be simply calculated. In addition, using the slew equation/table in the gate timing library, the gate output slew can, once again, also be simply calculated.
However, in very deep sub-micron (VDSM) technologies, the effect of interconnect resistive parasitics cannot be neglected. Using the sum of all load capacitances as the capacitive load is a simple, yet a quite inaccurate approximation, as described by J. Qian, S. Pullela, and L. Pillage, “Modeling the “effective capacitance” for the RC interconnect of CMOS gates,” IEEE Trans. on Computer Aided Design, vol. 13, pp. 1526-1535, 1994. A more accurate approximation for an nth order load seen by the gate/cell (i.e., a load with n distributed capacitances to ground) is to use a reduced order model. For instance, for the case of resistive capacitive interconnects, the load can be approximated by a second order RC-π model, as described by P. R. O'Brien and T. L. Savarino, “Modeling the driving-point characteristic of resistive interconnect for accurate delay estimation,” Proc. of International Conference on Computer Aided Design, pp. 512-515, 1989. Equating the first, second, and third moments of the admittance of the real load with the first, second, and third moments of the RC-π load, Cn, Rπ, and Cf 218, in FIG. 2(b), are determined. Note that the RC-π values are indeed a function of the input capacitance of any gates in the fan-out of the primitive gate. Using the “effective capacitance” technique, the reduced order model load (e.g., the RC-π load) is approximated by an equivalent capacitance. The delay and slew equations/tables are employed to obtain the gate delay and output transition time, given the slew 215 at the input of the gate and the reduced order RC-π load 218. It is worth mentioning that it is not straightforward to model the effect of the Miller capacitance on timing with the first and second driver modeling techniques, since the models do not explicitly account for the Miller capacitance. Using Current Source Driver Models (FIG. 3(c) (i.e., the third technique), which explicitly have the Miller capacitance in the model, one can evaluate the Miller capacitance effect on timing accurately.
Gate Timing Analysis Using Current Source Driver Model
Another form of CMOS driver modeling called the Current Source Driver Models will now be described. There are different types of current source modeling techniques such as the Composite Current Source (CCS) model and the Effective Current Source Model (ECSM), both known in the art, and CSM described by I. Keller, K. Tseng, N. Verghese, “A robust cell-level crosstalk delay change analysis,” Proceedings of International Conference on Computer-Aided Design (ICCAD), pp.147-154. The discussion that follows will be limited to the CSM model. However, it is straightforward to extend the discussion to another current source driver models as well.
A typical CSM model is shown in FIG. 3(c). The nonlinear CSM model consists of four elements: a nonlinear voltage-controlled current source driver, IDC(Vin, Vout) (i.e., the gate output DC current as a function of the input Vin and output Vout DC voltage levels) and three parasitic capacitances, i.e., the input capacitance to ground, Ci, the output capacitance to ground, Co, and the Miller capacitance from the input to the output, Cm. Note that the CSM driver model elements are independent from the output load and the input waveform (or the load connected to the input of the CMOS gate). Given the voltage waveform at the input, the load at the output of the CMOS gate and the CSM driver model of the gate, one may apply a nonlinear simulation to obtain the voltage waveform at the output of the CMOS gate. If properly employed, the CSM driver model will accurately capture the effect of Miller capacitance on timing. However, the nonlinear simulation is more inefficient than the Ceff calculation of the first and second driver modeling techniques, as previously discussed. Therefore, one may want to use the CSM modeling and a nonlinear simulation when the accuracy of the CSM driver modeling makes it necessary for accuracy purposes. Thus, when the Miller capacitance effect on timing is significant, it requires using the CSM modeling technique to achieve better accuracy.
Conventional Static Timing Analysis
STA propagates voltage waveforms from the circuit primary inputs through gates and interconnects to calculate the earliest/latest signal arrival times/voltage waveforms at the circuit primary outputs. Therefore, at any point of the circuit, if the voltage waveform at the input of the gate is calculated, STA performs a gate timing analysis to determine the voltage waveform at the output of the gate, using any of the driver modeling techniques previously described. In addition, at any point within the circuit, if the voltage waveform at the input of an interconnect network is calculated, STA employs interconnect timing analysis algorithms to calculate the voltage waveforms at the outputs of the interconnect network. Again, there is trade-off between accuracy and runtime to determine the order of the interconnect-reduced models for the interconnect timing analysis. STA has a linear complexity with respect to the number of the gates in a design by propagating the arrival times/required arrival times/voltage waveforms through the timing graph assuming that the timing stages are independent from each other (i.e., it considers a fixed load for the input capacitance of the gates in the fan-out of the primitive gates, while calculating the RC-π load as well as performing the interconnect timing analysis).
Referring now to the flowchart of a conventional STA flow shown in FIG. 4, in step 401, STA always begins by propagating the voltage waveforms from the circuit primary inputs toward the circuit primary outputs using the voltage waveforms at the primary input of the circuit. Next, for every gate or interconnect in the design, STA runs a gate timing analysis and interconnect timing analysis, respectively. Thus, as shown in step 402, STA checks if the voltage waveforms at the input of the next gate or next interconnect in the path are calculated. If the voltage waveform at the input of a gate is calculated, as shown in step 403, using the gate timing model, the input slew and the output load reduced order model (assuming that the input capacitance of the gates in the fan-out of the primitive gates have fixed values), STA runs the Ceff algorithm described earlier and calculates the gate propagation delay and output slew. If the voltage waveform at the input of an interconnect network is calculated, as shown in step 404, STA runs the interconnect timing analysis using the interconnect parasitics, the input slew and a fixed value for the input capacitance of each fan-out gate of the interconnect, and calculates the interconnect propagation delay and output slew at every output of the interconnect network. In step 405, STA checks if the gate and interconnect timing analysis has been performed for every gate and interconnect of the design and, thereby, the arrival time at every primary outputs of the design is calculated. If this is true, the static timing analysis of the circuit is complete. Otherwise, STA branches back to step 402 and continues.
From the aforementioned described considerations, it becomes evident that there exists a need in industry for an improved timing analysis in the process of propagating voltage waveforms/signal arrival times, such that for circuits where the Miller capacitance effect on timing is significant, a new interconnect and gate timing analysis flow is invoked, while for circuits where the Miller capacitance effect on timing is not significant, conventional gate and interconnect timing analysis algorithms are preferably employed. Such dual choice helps to maintain a linear STA run-time with respect to the number of gates in the design while, at the same time, increasing the accuracy of timing results with respect to a detailed SPICE analysis.